\section{Deque}
\subsection*{题意}

 给定一个双端队列 $a = (a_1, a_2, \ldots, a_n)$。现在有两名玩家轮流进行以下操作，直至队列为空：
 \begin{itemize}
\item 从队首或队尾取走一个数$c$，并且本次收益为$c$。
\end{itemize}

设先/后手的总收益分别为 $X$ 和 $Y$。先手想要最大化 $X-Y$，后手想要最大化 $Y-X$，即两人都想最大化自己与对手的差值。现两名玩家均以\textbf{最优策略}操作，请问最终 $X-Y$ 的值是多少？




\subsection*{数据范围}
\begin{itemize}
\item $1 \leq n \leq 3000$
\item $1 \leq a_i \leq 10^9$
\end{itemize}

\subsection*{题解}

其实本题核心就在 \textbf{“最优策略”}这四个字的定义。什么是最优策略？就是选取最坏情况下收益最高的决策。什么是最坏情况呢？这里当然不是指你脑子短路故意选取一个非最优解，而是指假设对方也会以最优策略决策。细心的同学会发现这里的定义是递归的，但这并没有关系，因为在只剩下一个数，或者更平凡的——序列为空的情况下，只存在一种决策供选择。

设 ${\texttt{dp}[i][j]}$ 表示序列为 $a_i,a_{i+1},\ldots,a_j$ 时，先手总收益减后手总收益的最大值。那么我们可以得到转移方程：
$$
{\texttt{dp}[i][j]} = \max(a_i - {\texttt{dp}[i+1][j]},a_{j} - {\texttt{dp}[i][j-1]})
$$

注意到上式中是减号的原因是，当前的先手在拿完后就变为下一轮的后手，所以当前先手的收益为下一轮中后手的收益。可能比较绕，多思考一下即可。


\subsection*{核心代码}
\inputminted[linenos,autogobble]{cpp}{./Code/L.cpp}
\newpage